/*
* 2010
* Authors: Dmitry Kolyanov <dk90.spb@gmail.com>, Ksenyia Cypan <ksenyiacypan@gmail.com>
*/

#pragma once

#include <boost/graph/adjacency_list.hpp>
#include <boost/unordered_map.hpp>

using namespace boost;

typedef double w_size_type;

typedef property <vertex_name_t, std::string, property <vertex_color_t, int >> vertex_p;  
typedef property < edge_weight_t, w_size_type > edge_p;

typedef adjacency_list<setS, vecS, undirectedS, vertex_p, edge_p> Graph;

typedef graph_traits<Graph>::edge_descriptor Edge;
typedef graph_traits<Graph>::vertex_descriptor Vertex;

typedef std::vector<Edge> Edge_set;
typedef std::vector<Vertex> Vertex_set;
typedef std::vector<Vertex> Group;

typedef std::pair<Edge_set*, w_size_type> Matching;
typedef std::vector<Matching> Matchings;
typedef std::pair<Group*, w_size_type> Obj_group;
typedef std::vector<Obj_group> Community;

namespace maxcut_t
{
	enum colors_t { gray, white, black };
};

class maxcut
{
private:
	w_size_type maxcut_size;	

	/*
	*combinatorial design approach to maxcut
	*/
	//Vertex ---> size_t
	boost::unordered_map<Vertex, size_t> vertices_numbers;
	size_t even_vertices_num;
	/*
	* hierarchial social metaheuristics for the maxcut
	*/

	//groups of individuals(nodes)
	Community groups;
	//numbers of Group for each vertex
	boost::unordered_map<Vertex, size_t> vertices_group_nums;

	/*
	* combinatorial design approach to maxcut
	*/

	//make graph with an even number of vertices
	void make_even_number_of_vertices(Graph &g);
	//preparation for algorithm
	void prepare_to_start(Graph &g, Matchings &matchings);
	//f : Vertex ---> size_t
	void create_vertex_mapping(const Graph &g);
	//return number of matching by given edge
	int number_of_matching(Edge e, const Graph &g);
	//fill matchings
	void create_matchings(const Graph &g, Matchings &matchings);
	//fill max_matching
	void fill_max_matching(Edge_set &es, Matchings &matchings);


	//varigated means that source is black, target is white, or vice versa 
	void variegated_out_edges(Edge e, Edge_set &var_out_edges, const Graph &g);
	void variegated_out_edges(Vertex v, Edge_set &var_out_edges, const Graph &g);
	bool is_varigated(Edge e, const Graph &g);
	//return size of var. edges set
	w_size_type varigated_size(Vertex u, Vertex v, Edge e, Graph &g);
	w_size_type varigated_size(Vertex u, int color, Graph &g);	

	//vertex v black?
	bool is_black(Vertex v, const Graph &g);
	//vertex v gray?
	bool is_gray(Vertex v, const Graph &g);
	//vertex v white?
	bool is_white(Vertex v, const Graph &g);
	//--||--
	void paint_black(Vertex v, Graph &g);
	void paint_white(Vertex v, Graph &g);
	void paint_gray(Vertex v, Graph &g);
	void paint_edge(Vertex u, Vertex v, Graph &g);
	//count total weight of given edge set
	w_size_type edge_set_size(const Edge_set &es, const Graph &g);
	//find all vertices, marked by gray color
	void create_gray_set(Vertex_set &gray_set, const Graph &g);

	/*
	* hierarchial social metaheuristics for the maxcut
	*/

	//total weight of edges, that connect given vertex v with core and perephery of given Group i
	std::pair<w_size_type, w_size_type> intermidiate_edges_weight(Vertex v, size_t i, const Graph &g);
	//weight of given group
	w_size_type group_weight(Community::iterator group, const Graph &g);
	//number of group with max weight
	size_t max_weight_group();
	size_t best_group_arg(size_t groups_size, Vertex v, size_t group_number, Graph &g);
	//functions for operations on groups
	void create_initial_groups(Graph &g);
	void update_groups(const Graph &g);


	//strategies for evolutional process
	void winner_strategy(size_t group_number, Graph &g);
	void loser_strategy(size_t group_number, Graph &g);

public:
	w_size_type get_maxcut_size();
	void genetic_algorithm(Graph &g);
	void combinatorial_algorithm(Graph &g);

	maxcut(void);
	~maxcut();
};